package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2 MB, 在所有 Go 提交中击败了67.26%的用户
 */
var row [9][9]bool
var col [9][9]bool
var cell [9][9]bool

func solveSudoku(board [][]byte) {

	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			row[i][j], col[i][j], cell[i][j] = false, false, false
		}
	}

	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] != '.' {
				t := board[i][j] - '1'
				row[i][t], col[j][t], cell[get(i, j)][t] = true, true, true
			}
		}
	}

	dfs(&board, 0, 0)
}

func dfs(board *[][]byte, x int, y int) bool {

	if y == 9 { x, y = x + 1, 0 }
	if x == 9 { return true }

	if (*board)[x][y] != '.' { return dfs(board, x, y + 1) }
	for i := 0; i < 9; i++ {
		if !row[x][i] && !col[y][i] && !cell[get(x, y)][i] {
			(*board)[x][y] = byte('1' + i)
			row[x][i], col[y][i], cell[get(x, y)][i] = true, true, true
			if dfs(board, x, y + 1) { return true }
			(*board)[x][y] = '.'
			row[x][i], col[y][i], cell[get(x, y)][i] = false, false, false
		}
	}
	return false
}

// 给定坐标(x, y), 返回九宫格编号
func get(x int, y int) int {
	return (x / 3) * 3 + y / 3
}

func OutputBasicArray2D(nums [][]byte) {

	fmt.Print("[")
	for i := 0; i < len(nums); i++ {
		if i > 0 && i < len(nums) { fmt.Print(" ") }
		fmt.Print("[")
		for j := 0; j < len(nums[i]); j++ {
			fmt.Printf("%c", nums[i][j])
			if j != len(nums[i]) - 1 { fmt.Print(", ") }
		}
		fmt.Print("]")
		if i != len(nums) - 1 { fmt.Println(", ") }
	}
	fmt.Println("]")
}

func main() {

	board := [][]byte{
		{'.', '9', '.', '.', '4', '.', '.', '.', '.'},
		{'1', '.', '.', '.', '.', '.', '6', '.', '.'},
		{'.', '.', '3', '.', '.', '.', '.', '.', '.'},
		{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
		{'.', '.', '.', '7', '.', '.', '.', '.', '.'},
		{'3', '.', '.', '.', '5', '.', '.', '.', '.'},
		{'.', '.', '7', '.', '.', '4', '.', '.', '.'},
		{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
		{'.', '.', '.', '.', '7', '.', '.', '.', '.'},
	}
	solveSudoku(board)
	OutputBasicArray2D(board)
}
